With the advance in computer technology in recent years, attempts have been made to recognize three dimensional shapes with a computer and apply the results to computer-aided design or CAD, texture mapping in computer graphics, finite element method and the like. For a computer to recognize three-dimensional shapes, a variety of recognition models have been employed such as by substituting a three-dimensional solid with a simpler figure such as a collection of cubes and having it recognized. A recognition model is generated using a solid that substantially represents the form of its input shape as intermediate data. A hexahedral mesh can be then generated by dividing the solid into a number of grids.
In general, a recognition model uses a solid that is defined in an integer space referenced as ijk space. All of the faces constituting the recognition model are defined to be parallel with any of ij, jk, and ki planes. At this point, a face that has the normal [i j k]=[1,0,0] is given the label “+I” as its attribute. As well, each of the faces is given any of the labels “+I”, “−I”, “+J”, “−J”, “+K”, and “−K”. Table 1 below shows the correspondence between each face and a normal defining the face.
TABLE 1Identification Label of FaceCorresponding Normal+I[1.0.0]−I[−1.0.0]+J[0.1.0]−J[0.−1.0]+K[0.0.1]−K[0.0.−1]
A recognition model is also represented in a so-called half-edge data structure that comprises a shell, faces, loops, half edges, and vertexes. A shell is a collection of faces; a face is comprised of an outer loop and a number of inner loops; and a loop is defined as a sequence of half edges. In accordance with the definition of recognition models, each half edge is supposed to be parallel with any of the axes i, j, and k. A half edge with its orientation [1,0,0] is given the label “+I” as its attribute, and as with faces, each half edge is classified as having any of the attributes “+I”, “−I”, “+J”, “−J”, “+K” and “−K”. FIG. 18 shows a recognition model and definition of labels to its faces and half edges. Unless orientations are not considered, the following description simply refers to a pair of corresponding half edges as an edge.
In general, a mesh generation method that uses a recognition model as intermediate data primarily comprises following four steps. FIG. 19 shows a conventional procedure of generating a recognition model. As shown, in generating a recognition model with a conventional method:
1) The surface of an inputted three-dimensional shape (FIG. 19(a)) is classified into portions having any of the attributes “+I”, “−I”, “+J”, “−J”, “+K”, and “−K” (FIG. 19(b)). FIG. 19(b) illustrates attributes labeled to respective faces and orientations of K, J, and I.
2) From the classified surface, a recognition model comprised of vertexes of hexahedrons is generated (FIG. 19(c)). As previously mentioned, each face of the recognition model is mapped to one face of a three dimensional shape's surface, edges are mapped to the boundaries of planes, and vertexes are mapped to the corner points of faces.
3) A mesh of a given size is used to divide the recognition model into grids to represent the model as a hexahedral mesh (FIG. 19(d)).
4) After fitting the hexahedral mesh in its inputted shape, smoothing process is applied for eliminating any distortions in the hexahedral elements to determine node coordinate values for the hexahedral mesh (FIG. 19(e)).
Various methods for generating a recognition model as intermediate data for mesh generation have been proposed, including, inter alia, Takahashi et al., “Keijouninshikio mochiita sanjigen-jidou-yousobunkatu-sisutemu no kaihatu (A Three-Dimensional Automatic Mesh Generation System Using Shape Recognition Technique)”, Transactions of the Japan Society of Mechanical Engineers (Series A), Vol. 59 (560), pp. 279-285, January 1993, Reza Taghavi, “Automatic Block Decomposition Using Fuzzy Logic Analysis” (9th International Meshing Roundtable, pp. 187-192, 2000), and, David R. White et al., “Automated Hexahedral Mesh Generation by Virtual Decomposition” (4th International Meshing Roundtable, 1995).
Takahashi et al. create a recognition model with any of the labels +I, −I, +J, and −J already assigned to each side of an inputted shape (an actual model). FIG. 20 illustrates the method of mesh generation by Takahashi et al. The number of segments belonging to each orientation is defined as Ns (s=(+I), (−I), (+J), or (−J)); the length of each side of an actual model is defined as ls,t(t=1, . . . , Ns); and the sum of the lengths of sides in each orientation is defined as Ls(s=(+I), (−I), (+J), or (−J)). On the other hand, the length of each side of a recognition model is defined as ms,t(t=1, . . . , Ns), and the sum of the lengths of sides in each orientation is defined as Ms(s=(+I), (−I), (+J), or (−J)). Ms,t is what need be determined. Since the definition of recognition models requires M(+I)=M(−I), M(+J)=M(−J), Ms is calculated with the following expression:
[Expression 1]M(+I)=M(−I)=(L(+I)+L(−I))/2M(+J)=M(−J)=(L(+J)+L(−J))/2
These expressions mean that Ms is determined as the average of opposite orientations. With these Ms values, ms,t can be derived using the following expression.
[Expression 2]ms,t=Ms×ls,t/Ls,t(s=(+I), (−I), (+J),or (−J), t=1, . . . , Ns)
The foregoing has shown how the length of each edge on a recognition model is calculated with the method proposed by Takahashi et al. This method, however, can be considered to merely calculate the lengths of edges on a recognition model so as to approximate them to the lengths of sides of an actual model, it thus does not ensure in any way that no between edges interference will occur on the recognition model.
As well, although the method by Taghavi et al. generates a recognition model as intermediate data, the method cannot address at all the problem of how to determine the number of divisions so that interference may not occur to a generated recognition model. And White discusses how hexahedrons can be generated inside a rectangular structured mesh when the rectangular structured mesh has been already provided on a surface. Since a structured mesh provided on a surface beforehand according to White already contains information on the number of divisions, the method can eliminate the necessity of calculating the number of divisions. However, White's method is disadvantageous in that it cannot be applied when a mesh on a surface has not been provided.
In addition, methods have been proposed that determine the number of edge divisions as an integer programming problem. Tam et al. (T. K. H. Tam, “Finite Element Mesh Control by Integer Programming”, International Journal for Numerical Methods in Engineering, Vol. 36, pp. 2581-2605, 1993) and Scott et al. (Scott A. Mitchell (“High Fidelity Interval Assignment”, 6th International Meshing Roundtable, 1997) propose methods for, when a coarse mesh has been already given, breaking it into a finer mesh. FIG. 21 shows how the method proposed by Tam et al. generates a structured mesh. Since Tam's method provides a coarse mesh in advance as shown in FIG. 21(a), it is assumed that the area has been divided into a set of convex shapes. The present case does not need the elimination of the interference of edges or faces since the interference of edges or faces has been already eliminated.
FIG. 22 illustrates another known method for determining the number of edge divisions as an integer programming problem. The mesh generation method in the FIG. 22, proposed by Mitchell (Scott A. Mitchell, High Fidelity Interval Assignment, 6th International Meshing Roundtable, 1997), addresses the determination of the number of divisions when a structured mesh and an unstructured mesh co-exist. However, the method only discloses the processing of convex shapes with respect to the generation of a structured mesh as with Tam.
Since many three-dimensional shapes have concave portions formed thereon, faces that include concave portions will be generated on a recognition model for a three-dimensional shape including concave portions. If a conventional method for generating a recognition model is applied to a three-dimensional shape that includes concave portions, an unexpected inconvenience may be encountered. FIG. 23 generally illustrates such an inconvenience as two-dimensional shapes for illustration. FIG. 23(a) shows an input shape and FIG. 23(b) shows a generated recognition model. With a conventional method, when the shape in FIG. 23(a) that includes a concave portion is input, degeneracy or interference of edges and faces can be generated depending on how the number of divisions is assigned to edges, potentially causing the inputted shape in FIG. 23(a) to give the inconsistent recognition model in FIG. 23(b). The example in FIG. 23 illustrates that the existence of a concave portion causes a mesh with degeneracy and interference. In the context of the invention, the degeneracy or interference of edges refers to edges overlapping one another or an edge intersecting with a face other than one that includes the edge. And the degeneracy or interference of faces means a face intersecting with another face or faces overlapping one another.
Although the conventional method in FIG. 23 addresses the inconvenience shown in FIG. 23(b) such as by a user manually generating an appropriate large mesh in advance, a computer could not determine the number of divisions in such a manner that degeneracy or interference would not occur to a solid that includes concave portions. Meanwhile, three-dimensional shapes that include concave portions as mentioned above can be seen commonly and is a general characteristic of various machine elements or real objects, making the problem of processing concave portions in conventional methods one of causes that limit generic applicability of recognition models.
That is, there has been a need that inconveniences with a recognition model such as degeneracy and interference can be automatically eliminated without producing situations such as one in which grids cannot generated because the numbers of divisions of opposite edges are unequal and thus an appropriate mesh for a three-dimensional solid cannot be generated. In addition, there has been a need that an appropriate recognition model for a three-dimensional solid can be generated and expressed as a mesh automatically with minimum manual operation.
The invention has been made in view of the above-mentioned disadvantages of the conventional methods, and has the object of providing a recognition model generation system, a method for generating a recognition model, a program for causing a computer to execute the method, a computer readable storage medium storing the program, and a structured mesh generation system that can divide an input three-dimensional shape appropriately and eliminate effort such as manually allocating a mesh without causing inconveniences like degeneracy and interference of faces or edges.